package HashBuck;

public class HashBuck {
    static class Node{
        public int key;
        public int val;
        public Node next;

        public Node(int key, int val) {
            this.key = key;
            this.val = val;
        }
    }

    // 用来存储链表的数组
    public Node[] array;
    public int usedSize;
    private static final float DEFAULT_LOAD_FACTOR=0.75f;

    public HashBuck(){
        array=new Node[10];
    }


    public void put(int key,int val){
        int index=key% array.length;

        Node cur=array[index];
        // 首先判断里面是否已经含有，如果有，则更新，没有则头插
        while(cur!=null){
            if(cur.key == key){
                cur.val=val;
            }
            cur= cur.next;
        }
        Node node=new Node(key, val);
        node.next=array[index];
        array[index]=node;
        usedSize++;

        // 插完之后要看里面 的负载因子 是否超过0.75
        if(loadfactor() > DEFAULT_LOAD_FACTOR){
            // 扩容
            resize();
        }
    }
    private float loadfactor(){
        return usedSize*1.0f / array.length;
    }
    private void resize(){
        // 先创建一个2倍大的数组桶
        Node[] newArray=new Node[2* array.length];

        for(int i=0;i< array.length;i++) {
            Node cur = array[i];
            while(cur!=null){
                Node tmp=cur.next;
                // 将原来的数据按照新的key进行调整
                int index=cur.key% newArray.length;
                // 头插法
                cur.next=newArray[index];
                newArray[index]=cur;
                cur=tmp;
            }
        }
        array=newArray;
    }


    public int get(int key){
        int index=key% array.length;
        Node cur=array[index];
        while(cur!=null){
            if(cur.key==key){
                return cur.val;
            }
            cur= cur.next;
        }
        return -1;
    }
}
